Матч 46, Путь короля (KingsTour)

Имеется шахматная доска 8*8, колонки которой пронумерованы буквами от ‘a’ до ‘h’, а строки цифрами от 1 до 8. Одной из шахматных фигур является пешка. Пешка бьет по диагонали. Например, находясь на с3, она угрожает полям b4 и d4.

Строки king, pawnA и pawnB описывают положение короля и двух пешек А и В на доске в формате “<буква><цифра>”. Необходимо найти наименьшее число ходов короля, за которое он сможет сбить пешку А. Король не может становиться под удар пешек и выходить за границы шахматного поля. При необходимости король может сбить пешку В. Пешки не двигаются.

Класс: KingsTour

Метод: int attackPawns(string king, string pawnA, string pawnB)

Ограничения: каждая строка king, pawnA и pawnB имеет формат <буква><цифра>, ‘a’ £ <буква> £ ‘h’, 1 £ <цифра> £ 8, начальные позиции короля и пешек различны, король не находится под ударом ни одной из пешек.

Вход. Строки king, pawnA и pawnB, задающие начальные позиции короля и двух пешек.

Выход. Наименьшее количество ходов короля, за которое он сможет сбить пешку А.

Пример входа

king	pawnA	pawnB
“c4”	“e6”	“d5”
“g2”	“a8”	“a2”
“a3”	“b1”	“c1”

Пример выхода

2

6

7

РЕШЕНИЕ

графы, поиск в ширину

Рассмотрим два варианта движения короля:

1. Король направляется к пешке А несмотря на положение пешки В и съедает ее;

2. Король направляется к пешке В, съедает ее и потом двигается к пешке А.

В обоих случаях при движении короля используется кратчайший путь, который находится поиском в ширину. Находим наименьшее количество ходов в первом и во втором случаях и возвращаем наименьшее среди них значение.

В поля, находящиеся под ударом пешек, изначально поставим значения 1000. Таким образом при поиске в ширину король на них не зайдет. Начальные положения короля и двух пешек занесем соответственно в переменные (kx, ky), (pax, pay), (pbx, pby). Запустим bfs(kx, ky). Занесем в переменные a и b наименьшее число ходов, которыми можно добраться до пешки А и В соответственно: a = m[pax][pay], b = m[pbx][pby]. Если пешка В сбивается, то следует запустить bfs(pbx, pby), найдя таким образом кратчайший путь от пешки В до А. Добавим к b значение m[pax][pay] после второго вызова bfs. Таким образом в a содержится длина кратчайшего пути короля до достижения цели без сбивания пешки В, а в b – со сбиванием. Возвращаем меньшее значение среди a и b.

ПРОГРАММА

#include <cstdio>

#include <string>

#include <memory>

#include <deque>

using namespace std;

int m[10][10];

deque<pair<int,int> > d;

int xx[8] = {1, 1, 1, -1, -1, -1, 0, 0};

int yy[8] = {-1, 0, 1, -1, 0, 1, 1, -1};

int cango(int x, int y)

{

if ((x < 1) || (x > 8) || (y < 1) || (y > 8) || (m[x][y] >= 0)) return 0;

return 1;

}

void bfs(int x, int y)

{

pair<int,int> temp;

int i;

m[x][y] = 0;

d.push_back(make_pair(x,y));

while(!d.empty())

{

temp = d[0]; d.pop_front();

for(i = 0; i < 8; i++)

if (cango(temp.first + xx[i],temp.second + yy[i]))

{

m[temp.first + xx[i]][temp.second + yy[i]] =

m[temp.first][temp.second] + 1;

d.push_back(make_pair(temp.first + xx[i],temp.second + yy[i]));

}

}

}

class KingsTour

{

public:

int attackPawns(string king, string pawnA, string pawnB)

{

int kx = king[0] - 'a' + 1, ky = king[1] - '1' + 1;

int pax = pawnA[0] - 'a' + 1, pay = pawnA[1] - '1' + 1;

int pbx = pawnB[0] - 'a' + 1, pby = pawnB[1] - '1' + 1;

int a, b;

memset(m,-1,sizeof(m));

m[pax-1][pay+1] = m[pax+1][pay+1] = 1000;

m[pbx-1][pby+1] = m[pbx+1][pby+1] = 1000;

bfs(kx,ky);

a = m[pax][pay]; b = m[pbx][pby];

memset(m,-1,sizeof(m));

m[pax-1][pay+1] = m[pax+1][pay+1] = 1000;

bfs(pbx,pby); b += m[pax][pay];

return (a < b) ? a : b;

}

};